package org.alanlau.structure;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU 主要由一个双向链表和hash表构成，需要注意的就是新增的时候，hash表也记得要新增，删除同样
 * @author liukun
 * @version 1.0
 * @date 2021/3/26 17:32
 */
public class LRUCache {
    static class DbList<K, V> {
        K key;
        V val;
        DbList<K, V> prev, next;

        DbList() {}

        DbList(K k, V v) {
            key = k;
            val = v;
        }
    }

    Map<Integer, DbList<Integer, Integer>> map;
    DbList<Integer, Integer> head, tail;
    /**
     * 缓存容量
     */
    int capacity;
    /**
     * 已缓存的数量
     */
    int size;

    public LRUCache(int capacity) {
        map = new HashMap<>();
        head = new DbList<>();
        tail = new DbList<>();
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
        size = 0;
    }

    public int get(int key) {
        DbList<Integer, Integer> x = map.get(key);
        if(null == x) {
            return -1;
        }
        makeRecently(key);
        return x.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(key);
            addLast(key, value);
            return;
        }
        if (size == capacity) {
            removeFirst();
        }
        addLast(key, value);
    }

    private void remove(int key) {
        DbList<Integer, Integer> x = map.get(key);
        if(null == x) {
            return;
        }

        x.prev.next = x.next;
        x.next.prev = x.prev;
        x.next = null;
        x.prev = null;

        map.remove(key);
        size--;
    }

    private void addLast(int key, int val) {
        DbList<Integer, Integer> x = new DbList<>(key, val);
        x.next = tail;
        x.prev = tail.prev;
        tail.prev.next = x;
        tail.prev = x;

        map.put(key, x);
        size++;
    }

    private void removeFirst() {
        if (size == 0) {
            return;
        }
        remove(head.next.key);
    }

    private void makeRecently(int key) {
        DbList<Integer, Integer> x = map.get(key);
        remove(key);
        addLast(x.key, x.val);
    }
}
